package cn.hycat.algorithm;

/**
 * @author 吕泽浩业
 * @version 1.0
 */
public class sort {
    public static void main(String[] args) {
        int[] arr = {9, 23, 7, 123, 23, 4, 3, 2, 1};
        insertSort(arr);
        printArr(arr);
    }


    //每一轮确定靠后的一位数字
    public static void bubbleSort(int[] arr) {
        for(int i = 0; i < arr.length; i++) {
            for(int j = 0 ; j < arr.length - i - 1; j++) {
                if(arr[j] > arr[j+1]) {
                    swap(arr, j, j+1);
                }
            }
        }
    }

    public static void selectSort(int[] arr) {
        int n = arr.length;
        for(int i = 0; i < n; i++) {
            int k = i;
            int temp = arr[i];
            for(int j = i + 1; j < n; j++)  {
                if(temp > arr[j]) {
                    k = j;
                    temp = arr[j];
                }
            }
            swap(arr, i, k);
        }
    }

    public static void insertSort(int[] arr) {
        int n = arr.length;
        for(int i = 1; i < n; i++) {
            for(int j = i; j >= 1; j--) {
                if(arr[j] < arr[j-1]) swap(arr, j, j-1);
                else break;
            }
        }
    }

    public static void printArr(int[] arr) {
        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
